Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into account the "lingering" of gradients: once a gradient is computed at x

First-order methods play a fundamental role in large-scale machine learning and optimization tasks. In most scenarios, the performance of a first-order method is represented by its convergence rate: the relationship between ε (the optimization error) versus T (the number of gradient computations). This is meaningful because in most applications, the time complexities for evaluating gradients at different points are of the same magnitude. In other words, the worse-case time complexities of first-order methods are usually proportional to a fixed parameter times T . In large-scale settings, however, if we have already spent time computing the (full) gradient at x, perhaps we can use such information to reduce the time complexity to compute full gradients at other points near x. We call this the "lingering" of gradients, because the gradient at x may be partially reused for future consideration, but will eventually fade away once we are far from x. Formally, consider the (finite-sum) stochastic convex minimization problem: { min

Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into account the ``lingering'' of gradients: once a gradient is computed at $x_k$, the additional time to compute gradients at $x_{k+1},x_{k+2},\dots$ may be reduced. We show how this improves the running time of gradient descent and SVRG. For instance, if the "additional time'' scales linearly with respect to the traveled distance, then the "convergence rate'' of gradient descent can be improved from $1/T$ to $\exp(-T^{1/3})$. On the empirical side, we solve a hypothetical revenue management problem on the Yahoo! Front Page Today Module application with 4.6m users to $10^{-6}$ error (or $10^{-12}$ dual error) using 6 passes of the dataset.

Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into account the ``lingering'' of gradients: once a gradient is computed at $x_k$, the additional time to compute gradients at $x_{k+1},x_{k+2},\dots$ may be reduced. We show how this improves the running time of gradient descent and SVRG. For instance, if the "additional time'' scales linearly with respect to the traveled distance, then the "convergence rate'' of gradient descent can be improved from $1/T$ to $\exp(-T^{1/3})$. On the empirical side, we solve a hypothetical revenue management problem on the Yahoo! Front Page Today Module application with 4.6m users to $10^{-6}$ error (or $10^{-12}$ dual error) using 6 passes of the dataset.